# https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/

# Python program to demonstrate delete operation
# in binary search tree 

# A Binary Tree Node 
class Node:

    # Constructor to create a new node
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None


# A utility function to do inorder traversal of BST 
def inorder(root):
    if root is not None:
        inorder(root.left)
        print(root.key)
        inorder(root.right)

    # A utility function to insert a new node with given key in BST


def insert(node, key):
    # If the tree is empty, return a new node
    if node is None:
        return Node(key)

    # Otherwise recur down the tree
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)

    # return the (unchanged) node pointer
    return node


# Given a non-empty binary search tree, return the node
# with minum key value found in that tree. Note that the 
# entire tree does not need to be searched 
def minValueNode(node):
    current = node

    # loop down to find the leftmost leaf
    while (current.left is not None):
        current = current.left

    return current

# 参考B站视频 https://www.bilibili.com/video/av33869443/?p=3
# Given a binary search tree and a key, this function
# delete the key and returns the new root 
def deleteNode(root, key):
    # Base Case
    if root is None:
        return root

    # If the key to be deleted is smaller than the root's
    # key then it lies in left subtree
    if key < root.key:
        root.left = deleteNode(root.left, key)

    # If the kye to be delete is greater than the root's key
    # then it lies in right subtree
    elif (key > root.key):
        root.right = deleteNode(root.right, key)

    # If key is same as root's key, then this is the node
    # to be deleted
    else:

        # Node with only one child or no child
        if root.left is None:
            temp = root.right
            root = None
            return temp

        elif root.right is None:
            temp = root.left
            root = None
            return temp

        # Node with two children: Get the inorder successor
        # 最后root.right = deleteNode(root.right, temp.key)其实转化成了
        # 前边 Node with only one child or no child 的情形
        ### 可以找左子树的最大值或者右子树的最小值作为successor
        ### 而左子树的最大值或者右子树的最小值必然只有一个或零个节点
        ### 所以转化成了前边 Node with only one child or no child 的情形
        # (smallest in the right subtree)
        temp = minValueNode(root.right)

        # Copy the inorder successor's content to this node
        root.key = temp.key

        # Delete the inorder successor
        root.right = deleteNode(root.right, temp.key)
    # 返回根节点
    return root


# Driver program to test above functions
""" 
Let us create following BST 
		  50 
		/	 \ 
	  30    70 
	  / \   / \ 
	20 40  60 80 
"""

root = None
root = insert(root, 50)
root = insert(root, 30)
root = insert(root, 20)
root = insert(root, 40)
root = insert(root, 70)
root = insert(root, 60)
root = insert(root, 80)

print("Inorder traversal of the given tree")
inorder(root)

print("\nDelete 20")
root = deleteNode(root, 20)
print(root.key)
print("Inorder traversal of the modified tree")
inorder(root)

print("\nDelete 30")
root = deleteNode(root, 30)
print(root.key)
print("Inorder traversal of the modified tree")
inorder(root)

print("\nDelete 50")
root = deleteNode(root, 50)
print(root.key)
print("Inorder traversal of the modified tree")
inorder(root)

# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
